package leetcode_700;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *RedundantConnection_684 判断一个多余路径里成环的那条边
 *describe:每加入一条边就判断有没有环 用深度优先搜索 AC 13% 用并查集 AC 100%
 *see:https://www.cnblogs.com/grandyang/p/7628977.html
 *2018年10月7日 下午4:29:01
 */
public class RedundantConnection_684_ {
	
	public static void main(String[] args) {
		RedundantConnection_684_ test=new RedundantConnection_684_();
		//int[][]edges =new int[][] {{1,2},{1,3},{2,3}};
		int[][]edges =new int[][] {{1,2},{2,3},{3,4},{1,4}};
		test.findRedundantConnection(edges);
	}
	
	
	public int[] findRedundantConnection(int[][] edges) {
		Map<Integer,List<Integer>> map=new HashMap<Integer,List<Integer>>();
		List<Integer> list0=new ArrayList<Integer>();
		List<Integer> list1=new ArrayList<Integer>();
		list0.add(edges[0][1]);
		list1.add(edges[0][0]);//避免空指针异常
		map.put(edges[0][0], list0);
		map.put(edges[0][1], list1);
        for(int i=1;i<edges.length;++i) {
        	if(help(map,edges[i][0],edges[i][1],new boolean [1001]))
        		return new int[] {edges[i][0],edges[i][1]};
        	List<Integer> now0=map.get(edges[i][0]);
        	if(now0==null) {
        		now0=new ArrayList<Integer>();
        	}
    		now0.add(edges[i][1]);
    		List<Integer> now1=map.get(edges[i][1]);
        	if(now1==null) {
        		now1=new ArrayList<Integer>();
        	}
    		now1.add(edges[i][0]);
    		map.put(edges[i][0], now0);
    		map.put(edges[i][1], now1);
        }
        return null;
    }
	
	
	/**
	 * describe:当遍历到一条边edge[i] 那么直接从edge[i][0]开始遍历 ， 看能否遍历到edge[i][1]
	 * 2018年10月7日 下午3:59:15
	 */
	public boolean help(Map<Integer,List<Integer>> map,int cur,int target,boolean visited[]) {
		if(visited[cur])
			return false;
		visited[cur]=true;
		List<Integer> list=map.get(cur);
		if(list!=null) {
			for(int i:list) {
				if(i==target)
					return true;
				if(help(map,i,target,visited)) {
					return true;
				}
			}
		}
		return false;
	}
	
	
	/**
	 * describe:并查集 完美解 AC 100%
	 * 2018年10月7日 下午4:39:41
	 */
	public int[] findRedundantConnection1(int[][] edges) {
        int[] sets = new int[edges.length + 1];
        
        for(int[] edge : edges) {
            int u = find(sets, edge[0]);
            int v = find(sets, edge[1]);  
            if(u == v) 
                return edge;
            sets[u] = v;//这里非常关键 相当于打通这个图
        }
        
        return new int[]{};
    }
    
    public int find(int[] sets, int v) {//没有找到就返回v 如果找到 就找到该点延伸最远的点
        return sets[v] == 0 ? v : find(sets, sets[v]);
    }
}
